package data_structure.mooc;

import data_structure.implement.QueueImp;

/**
 * A special queue based on the generic E
 * LoopQueue: having two index,one is "front",the other is "tail",when the "tail" or the "front" greater than the length,start the loop
 * Advantage:using the space adequately,delete operation:time complexity O(1)
 * Attention:
 * 1.the length=capacity+1,noting when constructor is initialed
 * 2.the real capacity is the length of the queue - 1
 * 3.front==tail means the queue is empty while (tail+1)%length==front means the queue is full
 *
 * @param <E>
 */
public class LoopQueue<E> implements QueueImp<E> {

    private E[] loopQueue;
    private int front, tail;
    private int size;

    /**
     * the length = capacity+1
     *
     * @param capacity int the initial data's capacity assigned by the user
     */
    public LoopQueue(int capacity) {
        loopQueue = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this (10);
    }


    @Override
    public boolean isEmpty() {
        return tail == front;
    }

    /**
     * add element in the tail of the queue
     *
     * @param e element
     */
    @Override
    public void enqueue(E e) {
        // check weather to resize
        if ((tail + 1) % loopQueue.length == front) {
            resize (getCapacity () * 2);
        }

        loopQueue[tail] = e;
        //tail may be looped
        tail = (tail + 1) % loopQueue.length;
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty ()) {
            throw new IllegalArgumentException ("the queue is empty");
        }

        E temp = loopQueue[front];
        loopQueue[front] = null;
        //every time ,deleting an element ,the front(the head of the queue,where data was removed)+1
        front = (front + 1) % loopQueue.length;
        size--;
        //getCapacity()/2 may be equal 0
        if (size == getCapacity () / 4 && getCapacity () / 2 != 0) {
            resize (getCapacity () / 2);
        }
        return temp;
    }

    /**
     * adjust the capacity of the queue with the size changing
     *
     * @param capacity capacity
     */
    private void resize(int capacity) {

        E[] newData = (E[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = loopQueue[(i + front) % loopQueue.length];
        }
        loopQueue = newData;
        //after resizing,initial "front" and "tail"
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder ();
        sb.append (String.format ("Queue size=%d capacity=%d", size, getCapacity ()));
        sb.append (" front[");
        for (int i = front; i != tail; i = (i + 1) % loopQueue.length) {
            sb.append (loopQueue[i]);
            //not the last element
            if ((i + 1) % loopQueue.length != tail) {
                sb.append (",");
            }
        }
        sb.append ("] tail");
        return sb.toString ();
    }

    /**
     * @return E the head element
     */
    @Override
    public E getFront() {
        if (isEmpty ()) {
            throw new IllegalArgumentException ("the queue is empty");
        }
        return loopQueue[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return loopQueue.length - 1;
    }

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<> (10);
        for (int i = 0; i < 10; i++) {
            queue.enqueue (i);
            System.out.println (queue.toString ());
        }

    }


}
